FLOW12 软件补丁问题

模型：

最小转移代价->最短路径

题意：

某公司发现其研制的一个软件中有 $n$ 个错误，随即为该软件发放了一批共 $m$ 个补丁程序。对于每一个补丁 $i$ ，都有 2 个与之相应的错误集合 $B_1(i)$ 和 $B_2(i)$ ，使得仅当软件包含 $B_1(i)$ 中的所有错误，而不包含 $B_2(i)$ 中的任何错误时，才可以使用补丁 $i$。补丁 $i$ 将修复软件中的某些错误 $F_1(i)$ ，而同时加入另一些错误 $F_2(i)$。另外，每个补丁都耗费一定的时间。 试设计一个算法，利用公司提供的 $m$ 个补丁程序将原软件修复成一个没有错误的软件，并使修复后的软件耗时最少。

题解：

又是一道假网络流题

一道巧妙的状压最短路

将每一种是否存在的状态各自看做一个节点

预处理出题面所说的四个集合$B_1$,$B_2$,$F_1$,$F_2$压缩后的状态

看看对于每种状态在使用了某个补丁后，会演变出什么新状态，据此连上一条边

由于边数会很多，所以可以在做最短路的同时对于当前状态，枚举每个补丁，看看会产生哪些新边，逐一处理

显然的，最短路起点为全1状态，终点为全0状态

最短路距离即答案

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

const int N=25,M=105,S=1<<20;
int dis[S],n,m,cost[M],f1[M],f2[M],b1[M],b2[M];
char a[N],b[N];

struct node{
    int x,v;
    inline bool operator < (const node &nt) const {
        return v>nt.v;
    }
};

void dij(int s){
    memset(dis,0x3f,sizeof dis);
    dis[s]=0;
    priority_queue<node> q;
    q.push((node){s,0});
    while(!q.empty()){
        node x=q.top();
        q.pop();
        if(dis[x.x]!=x.v) continue;
        for(int i=1;i<=m;i++) if((b1[i]&x.x)==b1[i]&&(b2[i]&x.x)==0){
            int y=((x.x|f1[i])^f1[i])|f2[i];
            if(dis[x.x]+cost[i]<dis[y]){
                dis[y]=dis[x.x]+cost[i];
                q.push((node){y,dis[y]});
            }
        }
    }
}

signed main(){
    read(n);read(m);
    for(int i=1;i<=m;i++){
        read(cost[i]);
        scanf("%s%s",a,b);
        for(int j=0;j<n;j++){
            if(a[j]=='+') b1[i]|=1<<j;
            if(a[j]=='-') b2[i]|=1<<j;
            if(b[j]=='-') f1[i]|=1<<j;
            if(b[j]=='+') f2[i]|=1<<j;
        }
    }
    dij((1<<n)-1);
    if(dis[0]==0x3f3f3f3f) dis[0]=0;
    write(dis[0]);
}